package leetcode_101_120;

import utils.TreeNode;

import java.util.List;
import java.util.Stack;

public class numDistinct_115 {
    /**
     * 统计并返回在 s 的 子序列 中 t 出现的个数
     * 结果需要对 109 + 7 取模。
     * s 和 t 由英文字母组成
     */
    public int numDistinct(String s, String t) {
        /**
         * 开始想法是使用二维数组记录每一个字符的位置、
         * 首先判断是否s中存在t子序列
         * 然后按子序列的顺序从后往前推，t[n]后的元素即t中n+1~len-1的元素s中出现的数量
         * 进行动态规划
         * 试了许久发觉实现起来难度有些大
         */
        char[] S=s.toCharArray();
        char[] T=t.toCharArray();
        Stack[] position=new Stack[26];
        for (int i=0;i<S.length;i++)
            position[S[i]-'0'].push(i);

        for(int i=T.length-1;i>=0;i--){
        }
        return  0;
    }

    public int numDistinct2(String s, String t) {
        /** 高解递归思路
         * 抓住 “选”，s 要照着 t 来挑选，逐字符考察选或不选，分别来到什么状态？
         *
         * 举例，s 为babgbag，t 为bag，末尾字符相同，于是 s 有两种选择：
         * 1，用s[s.length-1]去匹配掉t[t.length-1]，问题规模缩小：继续考察babgba和ba
         * 2，不这么做，但t[t.length-1]仍需被匹配，于是在babgba中继续挑，考察babgba和bag
         */
        return function(s.toCharArray(),t.toCharArray(),s.length()-1,t.length()-1);
    }

    public int function(char[] s,char[] t,int s_index,int t_index) {
        /**
         * 自己写的基础递归
         * 超时了
         */
        if (t_index < 0)  //如果能把t全部匹配完，就是一种匹配方法
            return 1;
        if (s_index < 0)
            return 0;
        if (s[s_index] == t[t_index])   //满足匹配条件时
            return function(s, t, s_index - 1, t_index - 1)  //进行匹配
                    + function(s, t, s_index - 1, t_index);         //不进行匹配
        return function(s, t, s_index - 1, t_index);
    }

    public int numDistinct3(String s, String t) {
        /**
         * 加入记忆化dp数组
         * 即如果此处之前已经处理过，直接跳过
         * 类似动态规划的递归写法
         */
        //记忆化递归
        int m = s.length() , n = t.length();
        if(m < n)
            return 0;
        int[][] dp = new int[m][n];
        //填充数组
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                dp[i][j] = -1;
        return helper(dp , m - 1, n - 1, s, t);
    }

    private int helper(int[][] dp , int i , int j , String s , String t)
    {
        if(j < 0)
            return 1;
        if(i < 0)
            return 0;
        if(dp[i][j] != -1)  //已经处理过，直接跳过
            return dp[i][j];
        if(s.charAt(i) == t.charAt(j))
            return dp[i][j] = helper(dp , i-1 , j-1 , s, t) + helper(dp , i-1, j , s, t);
        return dp[i][j] = helper(dp , i-1, j , s , t);
    }

    public int numDistinct4(String s, String t) {
        /**
         *动态规划写法
         * dp[i][j]：前 i 个字符的 s 子串中，出现前 j 个字符的 t 子串的次数。
         * 当s[i-1] != t[j-1]时，有dp[i][j] = dp[i-1][j]
         * 当s[i-1] == t[j-1]时，有dp[i][j] = dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
         */
        int m = s.length(), n = t.length();
        int[] dp = new int[n + 1];  //将二维转化为一维，节省空间
        /**
         *  只用了 i 行和 i-1 行的信息。 所以讲 i 行 j 列的数组 优化为 2行 j 列的数组。
         *  i-1 行的行数组只用到了第 j-1 个，所以将 j-1 行的行数组 优化为 一个变量 pre。
         */
        for (int i = 1; i <= m; i++) {
            int pre = 1;
            for (int j = 1; j <= n; j++) {
                int cur = dp[j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] += pre;
                }
                pre = cur;
            }
        }
        return dp[n];
    }
}
